package bfsAndDfs

// 存图：参考https://zhuanlan.zhihu.com/p/94890350
// 这里采用邻接表存图，例如
// 例如A->B, 则对应节点A，To表示的是下一个节点B，W表示的A到B的边的权值
type Edge struct {
	To int // 存储当前节点编号
	W  int // 存储上一个节点到该节点之间的边的权值
}

// 存图
var edges [][]Edge

// 存储节点的入度
var inDegree []int

// 添加节点from到节点to的有向图路径
func Add(from, to, w int) {
	e := Edge{
		To: to,
		W:  w,
	}
	edges[from] = append(edges[from], e)
}

// 添加无向图路径
func Add1(from, to, w int) {
	Add(from, to, w)
	Add(to, from, w)
}

// 统计所有节点的入度
func CountInDegree() {
	for _, v := range edges {
		for _, e := range v {
			inDegree[e.To]++
		}
	}
}

// 判断是否能进行拓扑排序，如果不能，则表示DAG中有环
// 拓扑排序-Kahn实现
// 时间复杂度:O(V+E)
// 空间复杂度:O(V+E)
func Toposort(n int) bool {
	var queue []int
	// 存储拓扑排序结果
	var result []int

	// 将所有入度为0的数存入队列中
	for i, v := range inDegree {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	// 拓扑排序
	for len(queue) != 0 {
		t := queue[0]
		result = append(result, t)
		queue = queue[1:]
		for _, e := range edges[t] {
			inDegree[e.To]--
			if inDegree[e.To] == 0 {
				queue = append(queue, e.To)
			}
		}
	}
	return n == len(result)
}
